package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _15_ThreeSum {
    public static void main(String[] args) {
        Solution solution = new _15_ThreeSum().new Solution();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = solution.threeSum(nums);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.println(integer);
            }
            System.out.println();
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> nSum(int[] nums, int n, int start, int target) {

            List<List<Integer>> list = new ArrayList<>();
            if (n == 2) {
                int l = start, r = nums.length - 1;
                while (l < r) {
                    int sum = nums[l] + nums[r];
                    if (sum == target) {
                        list.add(new ArrayList<Integer>(Arrays.asList(nums[l], nums[r])));
                        while (l + 1 < nums.length && nums[l + 1] == nums[l]) {
                            l++;
                        }
                        l++;
                    } else if (sum < target) {
                        l++;
                    } else if (sum > target) {
                        r--;
                    }
                }
                return list;
            } else {
                int i = start;
                while (i < nums.length) {
                    int num = nums[i];
                    List<List<Integer>> newList = nSum(nums, n - 1, i + 1, target - num);
                    if (newList.size() != 0) {
                        for (List<Integer> integerList : newList) {
                            integerList.add(num);
                            list.add(integerList);
                        }
                    }
                    while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
                        i++;
                    }
                    i++;
                }
                return list;
            }
        }

        public List<List<Integer>> threeSum(int[] nums) {
            // nums 需要先排好序
            Arrays.sort(nums);
            return nSum(nums, 3, 0, 0);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}